package com.taldh.algorithm.array;

import org.junit.Assert;
import org.junit.Test;

import java.util.stream.IntStream;

public class MoveZeroesSolution {
    /**
     * 283. 移动零
     *
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     *
     * 示例:
     *
     * 输入: [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * 说明:
     *
     * 必须在原数组上操作，不能拷贝额外的数组。
     * 尽量减少操作次数。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/move-zeroes
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     */
//    public void moveZeroes(int[] nums) {
//        IntStream.range(0, nums.length).forEach(i -> {
//            int nextNonZero = getNextNonZero(nums, i);
//            if (-1 == nextNonZero) {
//                return;
//            }
//            if (nums[i] == 0) {
//                nums[i] = nums[nextNonZero];
//                nums[nextNonZero] = 0;
//            }
//        });
//    }
//
//    public int getNextNonZero(int[] nums, int j) {
//        return IntStream.range(j, nums.length).filter(i -> nums[i] != 0).findFirst().orElse(-1);
//    }

    //复杂度：O(n^2) 空间 1
//    public void moveZeroes(int[] nums) {
//        int len = nums.length;
//        for (int i = 0; i < len - 1; i++) {
//            if (nums[i] == 0){
//                int firstNotZeroIndex = getFirstNotZeroIndex(nums, i);
//                if (firstNotZeroIndex == -1) {
//                    break;
//                }
//                swap(nums, i, firstNotZeroIndex);
//            }
//        }
//    }
//
//    private void swap(int[] nums, int i, int firstNotZeroIndex) {
//        nums[i] = nums[firstNotZeroIndex];
//        nums[firstNotZeroIndex] = 0;
//    }
//
//    private int getFirstNotZeroIndex(int[] nums, int i) {
//        int len = nums.length;
//        for (int j = i + 1; j < len; j++) {
//            if (nums[j] != 0) {
//                return j;
//            }
//        }
//        return -1;
//    }

    //复杂度： O(n)
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int lastNonZeroIndex = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0){
                nums[lastNonZeroIndex++] = nums[i];
            }
        }

        for (int i = lastNonZeroIndex; i < len; i++) {
            nums[i] = 0;
        }
    }

    @Test
    public void test() {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes(nums);
        Assert.assertArrayEquals(new int[]{1,3,12,0,0}, nums);
    }
}